package _03_myString;

import java.util.Arrays;

public final class MyString implements Comparable<MyString>, java.io.Serializable {

    private final char[] value;
    
    public MyString() {
        this.value = new char[0];
    }
    
    // 由字符串常量构造串
    public MyString(java.lang.String s) {
        // 复制s的所有字符
        this.value = new char[s.length()];
        for (int i = 0; i < this.value.length; i++) {
            this.value[i] = s.charAt(i);
        }
    }
    
    // 以value数组从i开始的n个字符构造串，i >= 0, n >= 0, i+n <= value.length
    // 若i或n指定序号越界，则抛出字符串序号越界异常
    public MyString(char[] value, int i, int n) {
        if (i >= 0 && n >= 0 && i+n <= value.length) {
            this.value = new char[n];
            for (int j = 0; j < n; j++) {
                this.value[j] = value[i+j];
            }
        } else {
            throw new StringIndexOutOfBoundsException("i = " + i + ", n = " + n + ", i + n = " + (i+n));
        }
    }
    
    // 以字符数组构造串
    public MyString(char[] value) {
        this(value, 0, value.length);
    }
    
    // 拷贝构造方法，深度拷贝，复制字符
    public MyString(MyString s) {
        this(s.value);
    }
    
    // 返回串长度，即字符数组容量
    public int length() {
        return this.value.length;
    }
    
    // 返回String类型的字符串
    public java.lang.String toString() {
        return new String(this.value);
    }
    
    // 返回第i个字符，0 <= i < length().若i越界，则抛出字符串序号越界异常
    public char charAt(int i) {
        if (i >= 0 && i < this.length()) {
            return this.value[i];
        }
        throw new StringIndexOutOfBoundsException(i);
    }
    
    // 返回序号从begin到end-1的子串，0 <= begin < length(), 0 <= end <= length(), begin < end
    public MyString substring(int begin, int end) {
        if (begin == 0 && end == this.value.length) {
            return this;
        }
        return new MyString(this.value, begin, end-begin);
    }
    
    public MyString substring(int begin) {
        return substring(begin, this.value.length);
    }
    
    // 返回this与s串连接生成的串。若s == null或""，则返回深拷贝的this
    public MyString concat(MyString s) {
        if (s == null || s.equals("")) {
            s = new MyString(this.value);
        }
        char[] buffer = new char[this.value.length + s.length()];
        int i;
        for (i = 0; i < this.value.length; i++) {
            buffer[i] = this.value[i];
        }
        for (i = this.value.length; i < buffer.length; i++) {
            buffer[i] = s.value[i];
        }
        return new MyString(buffer);
    }
    
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        if (!(obj instanceof MyString)) {
            return false;
        }
        MyString s = (MyString)obj;
        if (s.length() != this.length()) {
            return false;
        }
        for (int i = 0; i < this.length(); i++) {
            if (s.charAt(i) != this.charAt(i)) {
                return false;
            }
        }
        return true;
    }
    
    @Override
    public int compareTo(MyString s) {
        // TODO Auto-generated method stub
        for (int i = 0; i < this.length() && i < s.length(); i++) {
            if (this.value[i] != s.value[i]) {
                return this.value[i] - s.value[i];
            }
        }
        return this.length() - s.length();
    }
    
    // 返回this串删除所有空格的字符串
    public MyString trim() {
        char[] temp = new char[this.value.length];
        int j = 0;
        for (int i = 0; i < this.value.length; i++) {
            if (this.value[i] != ' ') {
                temp[j++] = this.value[i];
            }
        }
        return new MyString(temp, 0, j);
    }
    
    // 判断this串与str串是否相等，不考虑字母大小写
    public boolean equalsIgnoreCase(MyString str) {
        if (!(this.length() == str.length())) {
            return false;
        }
        for (int i = 0; i < this.length(); i++) {
            if (this.charAt(i) < 65 && this.charAt(i) > 97 && str.charAt(i) < 65 && str.charAt(i) > 97) {
                if (!(this.charAt(i) == str.charAt(i))) {
                    return false;
                }
            } else {
                if (!(this.charAt(i) == str.charAt(i) || this.charAt(i) == str.charAt(i) + 32 || this.charAt(i) + 32 == str.charAt(i))) {
                    return false;
                }
            }
        }
        return true;
    }
    
    // Brute-Force字符串匹配算法
    public int BFIndexOf(String pattern, int begin) {
        int m = pattern.length();
        int n = this.length();
        if (begin < 0) {
            begin = 0;
        }
        if (n == 0 || n < m || m > n - begin) {
            return -1;
        }
        int i = begin;
        int j = 0;
        while (i < this.length() && j < pattern.length()) {
            if (this.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
            } else {
                i = i - j + 1;
                j = 0;
                if (m > n - i) {
                    break;
                }
            }
        }
        return j == pattern.length() ? i-j : -1;
    }
    
    // KMP字符串匹配算法
    /*
    
    原理演示：
    目标串：aabaabaaf
    模式串：aabaaf
    当遍历到aabaab时，b不符合，此时因为aabaab的aab已经遍历过了而且符合模式串的前缀，那么不需要再回溯从头遍历，
    只需要继续往下遍历即可，那么从已经遍历的目标串后缀中找到最长的与模式串前缀相符的后缀即可知道要从哪开始往下遍历
    所以模式串如果是像aabaaf这种前缀在后面也出现过的形式，就可以直接在后面出现前缀处的地方往后开始遍历，而不用从头遍历
    以模式串aabaaf为例，前缀aa在后面重复出现过，那么当匹配时遍历到了后面的aa，就可以继续往后遍历
    那怎么确定往后遍历的索引呢？比如目标串匹配到aabaab，b不符合，但是作为目标串遍历的后缀aab是模式串的前缀，
    i不回溯还是从b开始，一直是自增1，而j呢？j应该从模式串aab的b开始遍历，也就是索引2开始
    前缀表数组next的作用就是实现这个索引的寻找
    
     */
    public int KMPIndexOf(String pattern, int begin) {
        int m = pattern.length();
        int n = this.length();
        if (begin < 0) {
            begin = 0;
        }
        if (n == 0 || n < m || m > n - begin) {
            return -1;
        }
        int[] next = getNext(pattern);
        int i = begin;
        int j = 0;
        while (i < n && j < m) {
            if (this.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
            } else {
                // 因为此时的j不匹配，上一个j才是匹配的，所以-1，减回来
                j = next[j-1];
                if (n - i < m - j) {
                    break;
                }
            }
        }
        return j == m ? i - m: -1;
    }
    
    // 返回模式串pattern的前缀表next数组，目标是在模式串中找到重复出现的最长前缀，而next则记录每个索引对应前缀出现的长度
    public int[] getNext(String pattern) {
        // TODO Auto-generated method stub
        /*
        // 书上的代码(用这串代码时，上面KMPIndex方法中j = next[j-1]要变成j = next[j])
        int j = 0;
        int k = -1;
        int[] next = new int[pattern.length()];
        next[0] = k;
        while (j < pattern.length() - 1) {
            if (k == -1 || pattern.charAt(j) == pattern.charAt(k)) {
                j++;
                k++;
                if (pattern.charAt(j) == pattern.charAt(k)) {
                    next[j] = next[k];
                } else {
                    next[j] = k;
                }
            } else {
                k = next[k];
            }
            // System.out.println(j + ", " + k + Arrays.toString(next));
        }
        return next;
        */
        // 书上preIndex初始为-1，当index遍历到与前缀索引0位置相等时，preIndex++变为0，同理，到1时preIndex为1，如果不相等再变为-1
        // 但是我还是习惯用它来记录前缀索引，从0开始，如果相等就++，遍历下一个，下一个相等再++，再下一个，如果不相等，就再从0开始
        int preIndex = 0;
        // 遍历模式串索引，pattern[0] == pattern[0]，前缀本身不算，直接跳过，从1开始遍历
        int index = 1;
        // 声明next数组
        int[] next = new int[pattern.length()];
        // 前缀本身位置不算，我这里记作0
        next[0] = 0;
        // 前缀索引最多遍历到pattern - 2，比如模式串是aaaa，前缀可以是a,aa,aaa，但不能是aaaa，因为这样就不算是重复出现的前缀了
        while (preIndex < pattern.length() - 1 && index < pattern.length()) {
            if (pattern.charAt(index) == pattern.charAt(preIndex)) {
                preIndex++;
            } else {
                preIndex = 0;
            }
            next[index] = preIndex;
            index++;
            System.out.println(index + ", " + preIndex + Arrays.toString(next));
        }
        return next;
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        System.out.println("测试字符串构造串以及字符数组构造串：");
        MyString ms0 = new MyString();
        MyString ms1 = new MyString("*");
        char[] ch2 = {'a', 'b', 'c', 'd'};
        MyString ms2 = new MyString(ch2);
        System.out.println(ms0 + ", " + ms1 + ", " + ms2);
        System.out.println("测试trim()方法：");
        MyString ms3 = new MyString("aBc dEf g");
        System.out.println(ms3.trim());
        System.out.println("测试equalsIgnoreCase(MyString)方法：");
        MyString ms4 = new MyString("AbC def G");
        System.out.println(ms3);
        System.out.println(ms4);
        System.out.println(ms3.equalsIgnoreCase(ms4));
        System.out.println("测试BFIndexOf(String, int)方法：");
        System.out.println(ms3.BFIndexOf(" g", 0));
        System.out.println("测试KMPIndexOf(String, int)方法：");
        MyString ms5 = new MyString("aabaabaaf");
        System.out.println(Arrays.toString(ms5.getNext("aabaaf")));
        System.out.println(ms5.KMPIndexOf("aabaaf", 0));
        
    }
}
